在一個文件中有10G個整數，亂序排列，要求找出中位數。內存限制為2G。只寫出思路即可（內存限制為2G意思是可以使用2G空間來運行程序，而不考慮本機上其他軟件內存占用情況。） 關于中位數：數據排序后，位置在最中間的數值。即將數據分成兩部分，一部分大于該數值，一部分小于該數值。中位數的位置：當樣本數為奇數時，中位數=(N+1)/2 ; 當樣本數為偶數時，中位數為N/2與1+N/2的均值（那么10G個數的中位數，就第5G大的數與第5G+1大的數的均值了）。

分析：既然要找中位數，很簡單就是排序的想法。那么基于字節的桶排序是一個可行的方法。

思想：將整型的每1byte作為一個關鍵字，也就是說一個整形可以拆成4個keys，而且最高位的keys越大，整數越大。如果高位keys相同，則比較次高位的keys。整個比較過程類似于字符串的字典序。

第一步:把10G整數每2G讀入一次內存，然后一次遍歷這536,870,912即（1024*1024*1024）*2 /4個數據。每個數據用位運算">>"取出最高8位(31-24)。這8bits(0-255)最多表示256個桶，那么可以根據8bit的值來確定丟入第幾個桶。最后把每個桶寫入一個磁盤文件中，同時在內存中統計每個桶內數據的數量NUM[256]。

代價：(1) 10G數據依次讀入內存的IO代價(這個是無法避免的，CPU不能直接在 磁盤上運算)。(2)在內存中遍歷536,870,912個數據，這是一個O(n)的線性時間復雜度。(3)把256個桶寫回到256個磁盤文件空間中，這個代價是額外的，也就是多付出一倍的10G數據轉移的時間。

第二步：根據內存中256個桶內的數量NUM[256]，計算中位數在第幾個桶中。很顯然，2,684,354,560個數中位數是第1,342,177,280個。假設前127個桶的數據量相加，發現少于1,342,177,280，把第128個桶數據量加上，大于1,342,177,280。說明，中位數必在 磁盤的第128個桶中。而且在這個桶的第1,342,177,280-N(0-127)個數位上。N(0-127)表示前127個桶的數據量之和。然后把第128個文件中的整數讀入內存。(若數據大致是均勻分布的，每個文件的大小估計在10G/256=40M左右，當然也不一定，但是超過2G的可能性很小)。注意，變態的情況下，這個需要讀入的第128號文件仍然大于2G，那么整個讀入仍然可以按照第一步分批來進行讀取。

代價：(1)循環計算255個桶中的數據量累加，需要O(M)的代價，其中m<255。(2)讀入一個大概80M左右文件大小的IO代價。

第三步：繼續以內存中的某個桶內整數的次高8bit（他們的最高8bit是一樣的）進行桶排序(23-16)。過程和第一步相同，也是256個桶。

第四步：一直下去，直到最低字節(7-0bit)的桶排序結束。我相信這個時候完全可以在內存中使用一次快排就可以了。

整個過程的 時間復雜在O(n)的線性級別上。但主要時間消耗在第一步的第二次內存-磁盤數據交換上，即10G數據分255個文件寫回磁盤上。一般而言，如果第二步過后，內存可以容納下存在中位數的某一個文件的話，直接快排就可以了。